package codingInterview.leetcode.editor.cn;

//把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。 
//
// 
//
// 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 
//
// 
//
// 示例 1: 
//
// 输入: 1
//输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
// 
//
// 示例 2: 
//
// 输入: 2
//输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0
//.05556,0.02778] 
//
// 
//
// 限制： 
//
// 1 <= n <= 11 
// Related Topics 数学 动态规划 概率与统计 👍 390 👎 0

import java.util.Arrays;

//Java：剑指 Offer 60 - n个骰子的点数
public class NgeTouZiDeDianShuLcof{
    public static void main(String[] args) {
                Solution solution = new NgeTouZiDeDianShuLcof().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /**        0 1 2 3 4 5 6 7 8 9 10 11 12
         * 一个骰子 0 1 1 1 1 1 1
         * 两个骰子 0 0 1 2 3 4 5 6 5 4 3  2  1
         */
    public double[] dicesProbability(int n) {
        if(n<1) return new double[0];
        int[][] count = new int[2][6*n+1];
        int flag=0;  // 通过0/1来切换前后数组
        for (int i = 1; i <= 6; i++)  // 初始化：一个骰子
            count[0][i]=1;
        for (int i = 2; i <= n ; i++) { // i个骰子
            flag=1-flag; // 切换数组
            // 重置，对于前i个点数，是不可能存在的，因为此时最小的点数就是i;
            for (int j = 0; j < i; j++)
                count[flag][j] =0;
            // 基于上次结果进行累加
            for (int j = i; j <= 6*i; j++) { // 点数为j时
                count[flag][j]=0; // 清除上上次的记录
                for (int k = 1; k <=j && k<=6; k++) {
                    //取上次记录的前六次之和，不足六个按不足的算,一般都是开头的几个(即k>j时)
                    count[flag][j]+=count[1-flag][j-k];
                }
            }

        }
        double sum = Math.pow(6,n); // 根据组合计算得到总情况
        double[] res = new double[6*n-n+1];
        for (int i = 0; i < 5 * n+1; i++)
            res[i] = count[flag][n+i]/sum;
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
